package mine.personal.demo.pratice.algorithm.dynamicprogramming.routes;

/**
 * @Author: lhl
 * @CreateTime: 2025-03-31
 * @Description: 动态规划算法集合
 * @Version: 1.0
 */
public class Solution {
    /**
     * leetcode 1137 -> 第N个泰波那契数
     *
     * @author: 李鸿麟
     * @date: 2025/3/31
     * @param: n
     * @return: int
     */
    public int tribonacci(int n) {
        int[] dp = new int[38];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        return dp[n];
    }

    public int tribonacci1(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        int dp1 = 0, dp2 = 1, dp3 = 1, ret = 0;
        for (int i = 3; i <= n; i++) {
            ret = dp1 + dp2 + dp3;
            dp1 = dp2;
            dp2 = dp3;
            dp3 = ret;
        }
        return ret;
    }

    /**
     * leetcode 面试题 3步问题
     *
     * @author: 李鸿麟
     * @date: 2025/4/1
     * @param: n
     * @return: int
     */
    public int waysToStep(int n) {
        if (n == 0 || n == 1) {
            return 1;
        } else if (n == 2) {
            return 2;
        } else if (n == 3) {
            return 4;
        }
        int dp1 = 1, dp2 = 2, dp3 = 4;
        int ret = 0;
        int MOD = (int) 1e9 + 7;
        for (int i = 4; i <= n; i++) {
            // 防溢出
            ret = ((dp1 + dp2) % MOD + dp3) % MOD;
            dp1 = dp2;
            dp2 = dp3;
            dp3 = ret;
        }
        return ret;
    }

    /**
     * leetcode -> 最小花费爬楼梯
     *
     * @author: 李鸿麟
     * @date: 2025/4/4
     * @param: cost
     * @return: int
     */
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        for (int i = 2; i <= cost.length; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }

    /**
     * leetcode -> 解码方法(未添加辅助节点的初始化)
     *
     * @author: 李鸿麟
     * @date: 2025/4/5
     * @param: s
     * @return: int
     */
    // 这个没有优化过的代码看起来比较冗余 事实上动态规划的思想还是体现的非常好的
    public static int numDecodings(String s) {
        int l = s.length();
        char[] charArray = s.toCharArray();
        int[] dp = new int[l];
        // 初始化过程虽然看起来麻烦 但是是严格根据题意来的
        // 如果第1位就无法编码 则从位置1开始的字符串都是无法编码的
        if (charArray[0] != '0') {
            dp[0]++;
        }
        // 边界情况处理
        if (l == 1) {
            return dp[0];
        }
        // 依据题意 '"16"有两种编码方式 所以要单独处理
        // 第1位和第2位分开均可正常编码
        if (charArray[1] != '0' && charArray[0] != '0') {
            dp[1]++;
        }
        // 第1位和第2位组合在一起可以编码
        int t = (charArray[0] - '0') * 10 + charArray[1] - '0';
        if (t >= 10 && t <= 26) {
            dp[1]++;
        }

        // 动态规划过程
        for (int i = 2; i < l; i++) {
            if (charArray[i] != '0') {
                dp[i] += dp[i - 1];
            }
            int tt = (charArray[i - 1] - '0') * 10 + charArray[i] - '0';
            if (tt >= 10 && tt <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[l - 1];
    }

    /**
     * leetcode -> 解码方法(添加了辅助节点的初始化)
     *
     * @author: 李鸿麟
     * @date: 2025/4/5
     * @param: s
     * @return: int
     */
    // 为什么要添加辅助节点 -> 1.减少代码量 2.实现代码统一
    public static int numDecodings2(String s) {
        int l = s.length();
        char[] charArray = s.toCharArray();
        // 为什么这里要给dp数组多开1位? 我个人的理解如下:
        // 1.更利于人脑的思考 -> 在针对字符串的讨论中 字符串的第一个字母我们都说是第1位 但是数组的第1位下标是0 为了方便思考 故给dp数组多开1位
        // 2.可以实现代码的统一 -> 在之前没有添加辅助节点的解法中 初始化的逻辑和后续for循环内的遍历逻辑是非常像的 给dp数组多开1位 相当于把旧dp数组的内容水平右移1位 那么原来的初始化逻辑就可以放在for循环里了
        int[] dp = new int[l + 1];
        // 为什么dp[0] = 1?
        // 在计算dp[2]的时候 实则是在计算charArray[1] 也就是字符串的第二位 依据状态转移方程:dp[i] = dp[i-1] + dp[i-2]可知 计算dp[2]需要知道dp[1]和dp[0]的具体值
        // 但是由于辅助节点的问题dp[2]的计算由先前人为的初始化转移到了循环里 当i=2时 如果charArray[2-1]和charArray[2-2] 也就是字符串的第1位和第2位单独和组合都可以正确编码 则charArray[1]对应的dp值应该为2
        // 如果dp[0]还赋值为0 就相当于少算了一种情况 dp[2]的计算就不正确了 这里我认为还有一个很妙的点 -> 状态转移方程是分开计算的 即如果charArray[i-2]和charArray[i-1]的组合如果可以被编码 dp[i-2]才会被dp[i]计算
        // 所以dp[0]虽然赋值了1 但是如果charArray[1]不能和charArray[0]形成一对合法编码值 那么dp[0]也不会被计算进去 即dp[2]只会+=dp[1]
        dp[0] = 1;
        // 故意写成这样的 加深下表的映射关系
        if (charArray[1 - 1] != '0') {
            dp[1]++;
        }

        // 动态规划过程
        for (int i = 2; i <= l; i++) {
            if (charArray[i - 1] != '0') {
                dp[i] += dp[i - 1];
            }
            int tt = (charArray[i - 2] - '0') * 10 + charArray[i - 1] - '0';
            if (tt >= 10 && tt <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        // 注意下标映射
        return dp[l];
    }

    /**
     * leetcode -> 不同路径
     *
     * @author: 李鸿麟
     * @date: 2025/4/6
     * @param: m
     * @param: n
     * @return: int
     */
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }

    /**
     * leetcode -> 不同路径II
     *
     * @author: 李鸿麟
     * @date: 2025/4/7
     * @param: obstacleGrid
     * @return: int
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (obstacleGrid[i - 1][j - 1] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }

    /**
     * leetcode -> 珠宝的最大价值
     *
     * @author: 李鸿麟
     * @date: 2025/4/7
     * @param: frame
     * @return: int
     */
    public int jewelleryValue(int[][] frame) {
        int m = frame.length, n = frame[0].length;
        if (m == 1 && n == 1) {
            return 0;
        }
        int[][] value = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                value[i][j] = Math.max(value[i - 1][j], value[i][j - 1]) + frame[i - 1][j - 1];
            }
        }
        return value[m][n];
    }

    /**
     * leetcode -> 下降路径的最小和
     *
     * @author: 李鸿麟
     * @date: 2025/4/8
     * @param: matrix
     * @return: int
     */
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;

        int[][] dp = new int[n + 1][n + 2];

        for (int i = 1; i <= n; i++) {
            dp[i][0] = dp[i][n + 1] = Integer.MAX_VALUE;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                int x = dp[i - 1][j - 1];
                int y = dp[i - 1][j];
                int z = dp[i - 1][j + 1];
                dp[i][j] = Math.min(Math.min(x, y), z) + matrix[i - 1][j - 1];
            }
        }
        int ret = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            ret = Math.min(ret, dp[n][i]);
        }
        return ret;
    }

    /**
     * leetcode -> 最小路径和
     *
     * @author: 李鸿麟
     * @date: 2025/4/9
     * @param: grid
     * @return: int
     */
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        //确定dp数组
        int[][] dp = new int[m + 1][n + 1];

        //初始化dp数组 多开的一行和一列都初始化成"无穷大" 避免对其他元素求和时造成影响
        for (int i = 0; i <= m; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }
        for (int i = 0; i <= n; i++) {
            dp[0][i] = Integer.MAX_VALUE;
        }
        // grid数组最上面需要初始化成0 避免无穷大的影响
        dp[0][1] = 0;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }

    /**
     * leetcode -> 地下城游戏
     *
     * @author: 李鸿麟
     * @date: 2025/4/12
     * @param: dungeon
     * @return: int
     */
    public static int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m + 1][n + 1];

        for (int j = 0; j <= n; j++) {
            dp[m][j] = Integer.MAX_VALUE;
        }
        for (int i = 0; i <= m; i++) {
            dp[i][n] = Integer.MAX_VALUE;
        }
        dp[m][n - 1] = dp[m - 1][n] = 1;

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int t = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = Math.max(1, t);
            }
        }
        return dp[0][0];
    }

    public static void main(String[] args) {
        //int[][] arr = {{-2, -3, 3}, {-5, -10, 1}, {10, 30, -5}};
        int[][] arr = {{0}};
        System.out.println(calculateMinimumHP(arr));
    }
}
